'''
https://leetcode.cn/problems/insert-delete-getrandom-o1/description/
'''
import random


class RandomizedSet:

    def __init__(self):
        self.data = [-1] * 32
        self.size = 0
        self.idx_dict = {}

    def insert(self, val: int) -> bool:
        if val in self.idx_dict:
            return False
        self.idx_dict[val] = self.size
        if self.size >= len(self.data) - 1:
            self.data *= 2
        self.data[self.size] = val
        self.size += 1
        return True

    def remove(self, val: int) -> bool:
        if val not in self.idx_dict:
            return False
        i = self.idx_dict[val]
        if i == self.size - 1:
            del self.idx_dict[val]
        else:
            self.data[i], self.data[self.size - 1] = self.data[self.size - 1], self.data[i]     # 不直接删，伪删除
            del self.idx_dict[val]
            self.idx_dict[self.data[i]] = i
        self.size -= 1
        return True

    def getRandom(self) -> int:
        return self.data[random.randint(0, self.size - 1)]

class RandomizedSet2:

    def __init__(self):
        self.sets = set()

    def insert(self, val: int) -> bool:
        if val in self.sets:
            return False
        self.sets.add(val)
        return True

    def remove(self, val: int) -> bool:
        if val not in self.sets:
            return False
        self.sets.remove(val)
        return True

    def getRandom(self) -> int:
        return random.choice(list(self.sets))

# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# obj.insert(0)
# obj.insert(1)
# obj.remove(0)
# obj.insert(2)
# obj.remove(1)
# print(obj.getRandom())